package interview.algorithms.array;

import common.Util;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 2018/5/15 16:18
 */
public class Solution {
    /*top K问题的解法
    1.排序   时间复杂度 O(nlgn)
    2.利用最小堆   时间复杂度 O(n * lgk) 可利用java中的优先队列. 底层是二叉堆.
    3.快速排序中的划分   时间复杂度 O(n)*/

    public  int KthLargest(int[] a, int k) {
        Arrays.sort(a);
        return a[a.length - k];
    }
    public  int KthLargestII(int[] a, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < a.length; i++) {
            heap.offer(a[i]);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.peek();
    }

    public  int KthLargestIII(int[] a, int k) {
        k = a.length - k;
        int lo = 0;
        int hi = a.length - 1;
        while (lo < hi) {
            int j = partition(a,lo,hi);
            if (j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return a[k];
    }
    private int partition(int[] a,int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            Util.swap(a,i,j);

        }
        Util.swap(a,lo,j);
        return j;
    }


    /**
     * 右移k 位
     * @param a
     * @param k
     */
    public void shiftK(int[] a, int k) {
        int n = a.length;
        k = k % n;
        reverse(a,0,k - 1);
        reverse(a,k,n - 1);
        reverse(a,0,n - 1);
    }
    private void reverse(int[] a, int i,int j) {
        for (;i < j;i++,j--) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }


    /**
     *转圈打印矩阵
     * @param martix
     */
    public void spiralOrderPrint(int[][] martix) {
        int tR = 0;
        int tC = 0;
        int dR = martix.length - 1;
        int dC = martix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            printEdge(martix,tR++,tC++,dR--,dC--);
        }
    }
    private void printEdge(int[][] martix,int tR,int tC,int dR,int dC) {
        if (tR == dR) {
            for (int i = tC; i < dC; i++) {
                System.out.print(martix[tR][i] + " ");
            }
        } else if (tC == dC) {
            for (int i = tR; i < dR; i++) {
                System.out.print(martix[i][tC] + " ");
            }
        } else {
            int curR = tR;
            int curC = tC;
            while (curC != dC) {
                System.out.println(martix[curR][curC] + " ");
                curC++;
            }
            while (curR != dR) {
                System.out.println(martix[curR][curC] + " ");
                curR++;
            }
            while (curC != tC) {
                System.out.println(martix[curR][curC] + " ");
                curC--;
            }
            while (curR != tR) {
                System.out.println(martix[curR][curC] + " ");
                curR--;
            }
        }
    }


    /**
     * 560. 和为K的子数组
     * @param nums
     * @param k
     * @return
     */
    public int subarraySumI(int[] nums, int k) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (Util.sum(nums,i,j) == k) {
                    res++;
                }
            }
        }
        return res;
    }
    public int subarraySumII(int[] nums, int k) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int count = 0;
        int[] sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= nums.length; j++) {
                if (sum[j] - sum[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }


    /**
     * 697. 数组的度
     * bf  超时
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int degree = getDegree(nums,0,nums.length - 1);
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (degree == getDegree(nums,i,j)) {
                    res = Math.min(res,j - i + 1);
                }
            }
        }
        return res;
    }
    private int getDegree(int[] a,int lo, int hi) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = lo; i <= hi; i++) {
            if (!map.containsKey(a[i])) {
                map.put(a[i],1);
            } else {
                map.put(a[i],map.get(a[i]) + 1);
            }
        }
        Collection<Integer> collection = map.values();
        int max = 0;
        for (Integer i : collection) {
            max = Math.max(max,i);
        }
        return max;
    }

    public int findShortestSubArrayII(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        Map<Integer,Integer> left = new HashMap<>();
        Map<Integer,Integer> right = new HashMap<>();
        Map<Integer,Integer> count = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            left.putIfAbsent(x, i);
            right.put(x,i);
            count.put(x,count.getOrDefault(x,0) + 1);
        }

        int res = nums.length;
        int degree = Collections.max(count.values());
        for (int x : count.keySet()) {
            if (count.get(x) == degree) {
                res = Math.min(res,right.get(x) - left.get(x) + 1);
            }
        }
        return res;
    }

    /**
     * 74. 搜索二维矩阵
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length < 1 || matrix[0] == null || matrix[0].length < 1) {
            return false;
        }

        int row = matrix.length;
        int col = matrix[0].length;
        int i = 0;
        int j = col - 1;
        while (i < row && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }

    /**
     * 55. 跳跃游戏
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length < 1) {
            return false;
        }
        int cur = 0;
        int next = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (cur < i) {
                cur = next;
                if (next < i) {
                    return false;
                }
            }
            next = Math.max(next,i + nums[i]);
        }
        return next >= nums.length - 1;
    }

    /**
     * 45. 跳跃游戏 II
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int cur = 0;
        int next = 0;
        int jump = 0;
        for (int i = 0; i < nums.length; i++) {
            if (cur < i) {
                jump++;
                cur = next;
            }
            next = Math.max(next,i + nums[i]);
        }
        return jump;
    }

    /**
     * 56. 合并区间
     * @param intervals
     * @return
     */
    public List<Interval> merge(List<Interval> intervals) {
        LinkedList<Interval> res = new LinkedList<>();
        Collections.sort(intervals, (o1, o2) -> o1.start > o2.start ? 1 : o1.start == o2.start ? 0 : -1);

        for (Interval interval : intervals) {
            if (res.isEmpty() || res.getLast().end < interval.start) {
                res.add(interval);
            } else {
                res.getLast().end = Math.max(res.getLast().end,interval.end);
            }
        }
        return res;
    }

    /**
     * 79. 单词搜索
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        if (board == null && word == null) {
            return true;
        }
        boolean[][] used = new boolean[board.length][ board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (word.charAt(0) == board[i][j] && existCore(board,word,used,i,j,0)) {
                    return true;
                }
            }
        }
       return false;
    }
    private boolean existCore(char[][] board, String word,boolean[][] used,int i,int j,int index) {
        if (index == word.length()) {
            return true;
        }
        if (i >= board.length || i < 0 || j >= board[i].length || j < 0 ||
                used[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }
       used[i][j] = true;
        if (existCore(board,word,used,i - 1,j,index + 1) ||
                existCore(board,word,used,i + 1,j,index + 1) ||
                existCore(board,word,used,i,j - 1,index + 1) ||
                existCore(board,word,used,i ,j + 1,index + 1)) {
            return true;
        }
        used[i][j] = false;
        return false;

    }

    /**
     * 54. 螺旋矩阵
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length < 1) {
            return res;
        }
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            spiralOrderCore(matrix,tR++,tC++,dR--,dC--,res);
        }
        return res;
    }
    private void spiralOrderCore(int [][] matrix, int tR, int tC, int dR, int dC,List<Integer> res) {
        if (tR == dR) {
            for (int i = tC; i <= dC; i++) {
                res.add(matrix[tR][i]);
            }
        } else if (tC == dC) {
            for (int i = tR; i <= dR; i++) {
                res.add(matrix[i][tC]);
            }
        } else {
            int curC = tC;
            int curR = tR;
            while (curC != dC) {
                res.add(matrix[curR][curC]);
                curC++;
            }
            while (curR != dR) {
                res.add(matrix[curR][curC]);
                curR++;
            }while (curC != tC) {
                res.add(matrix[curR][curC]);
                curC--;
            }while (curR != tR) {
                res.add(matrix[curR][curC]);
                curR--;
            }
        }
    }
    /**
     * 59. 螺旋矩阵 II
     * @param n
     * @return
     */
    public  int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int left = 0,top = 0;
        int right = n - 1,down = n - 1;
        int cnt = 1;
        while (left <= right) {
            for (int i = left; i <= right; i++) {
                res[top][i] = cnt++;
            }
            top++;
            for (int i = top; i <= down; i++) {
                res[i][right] = cnt++;
            }
            right--;
            for (int i = right; i >= left; i--) {
                res[down][i] = cnt++;
            }
            down--;
            for (int i = down; i >= top; i--) {
                res[i][left] = cnt++;
            }
            left++;
        }
        return res;
    }

    /**
     * 90. 子集 II
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsetsWithDup(res,new ArrayList<>(),nums,0);
        return res;
    }
    private void backtrackForSubsetsWithDup(List<List<Integer>> res, List<Integer> tmpList,int[] nums, int start) {
        res.add(new ArrayList<>(tmpList));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            tmpList.add(nums[i]);
            backtrackForSubsetsWithDup(res,tmpList,nums,i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }
    @Test
    public void test() {
        int[] nums1 = {0,2,3};
        shiftK(nums1,2);
        for (int i = 0; i < nums1.length - 1; i++) {
            System.out.print(nums1[i] + " ");
        }
        System.out.println(nums1[nums1.length - 1]);


        /*int[] nums = {1, 2, 2, 3, 1};
        int[] nums1 = {1,2,2,3,1,4,2};
        System.out.println(findShortestSubArray(nums));
        System.out.println(findShortestSubArray(nums1));
*/
        /*int[] nums = {1,2,1};
        System.out.println(subarraySumII(nums,3));*/
    }

    class Interval {
     int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
  }
}
